package com.lun.swordtowardoffer2.c08;

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class InorderSuccessor {

	//方法一：时间复杂度O(n)的解法-中序迭代遍历
	public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
		LinkedList<TreeNode> stack = new LinkedList<>();
		TreeNode cur = root;
		boolean found = false;
		while(!stack.isEmpty() || cur != null) {
			if(cur != null) {
				stack.push(cur);
				cur = cur.left;
			}else {
				cur = stack.pop();
				
				if(found) {
					break;
				}
				if(cur == p) {
					found = true;
				}
								
				cur = cur.right;
			}
		}
		return cur;
	}
	
	//方法二：时间复杂度O(h)的解法-二分查找
	public TreeNode inorderSuccessor2(TreeNode root, TreeNode p) {
		TreeNode cur = root;
		TreeNode result = null;
		
		while(cur != null) {
			if(cur.val > p.val) {
				result = cur;
				cur = cur.left;
			}else {
				cur = cur.right;
			}
		}
		
		return result;
	}
	
}
